package leetcode.pre50;

import java.util.Arrays;

/**
 * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 * <p>
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * <p>
 * 必须原地修改，只允许使用额外常数空间。
 * <p>
 * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-permutation

 * TODO 获取下一个全排列:{@link leetcode.top100.Code31_NextPermutation}
 * TODO 获取第k个全排列, O(kn)
 * TODO 全排列：使用swap或者使用next全排列，时间复杂度O(n!)
 * TODO 字典序全排列：使用swap最后排序是O(n!log(n!))，使用nextO(n!)

 * @date 2020/6/2 20:05
 */
public class Code31_NextPermutation_下一个全排列 {

    public static void main(String[] args) {
        Code31_NextPermutation_下一个全排列 s = new Code31_NextPermutation_下一个全排列();
        int[] nums = {1, 2, 3};
        int n = nums.length;
        for (int i = n - 1; i >= 1; i--) {
            n *= i;
        }
        for (int i = 0; i < n - 1; i++) {
            s.nextPermutation(nums);
            System.out.println(Arrays.toString(nums));
        }

    }

    /**
     * 6 3 5 4 2 1
     * 1、从最后一位开始往前找，找到第一个递减的，3 = target = nums[i] < nums[i+1]
     * 2、从最后一位开始往前找，找到第一个 4 = num > target
     * 3、交换num与target 6 4 5 3 2 1，从i后开始反转   6 4 1 2 3 5
     *
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        //5 4 3 2 1这种，下一个全排列是1，2，3，4，5
        if (i < 0) {
            reverse(nums, i + 1, nums.length - 1);
            return;
        }
        int j = nums.length - 1;
        while (j >= 0 && nums[i] >= nums[j]) j--;
        swap(nums, i, j);
        reverse(nums, i + 1, nums.length - 1);
    }

    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }

    private void swap(int[] nums, int i, int j) {
        if (i == j) return;
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }
}
